This application is based on Japanese Patent Application No. 10-127738 filed May 11, 1998, which application is incorporated herein by reference in its entirety.
1. Field of the Invention
The present invention relates to a symbolic calculation system and a symbolic calculation method, both for performing a symbolic calculation to solve simultaneous linear equations, and also relates to a parallel circuit simulation system which effects a circuit simulation by solving the simultaneous linear equations.
2. Description of the Related Art
Generally speaking, a process for solving simultaneous linear equations involves a symbolic calculation process and a numerical calculation process. An example of the symbolic calculation process, involved in the process for solving simultaneous linear equations, is described in the third section xe2x80x9cSparse Matrix Methodsxe2x80x9d of xe2x80x9cFundamentals of Computer-Aided Circuit Simulationxe2x80x9d (written by William J. McCalla and published in 1988).
FIG. 11 is a flowchart showing the symbolic calculation process involved in the aforementioned conventional process for solving simultaneous linear equations.
Firstly, a single entry set E is prepared, and information (entries) specifying the positions of nonzero elements contained in a coefficient matrix is sequentially added to the entry set E. Further, an array R(k) representing the number of entries contained in the kth row and an array C(k) representing the number of entries contained in the kth column are also prepared and updated at the time of adding the entries (a step S410).
Next, the use of a variable i, representing a count which is incremented each time the symbolic calculation process is repeated, is declared, and the initialization procedure of substituting the value xe2x80x9c1xe2x80x9d for xe2x80x9cixe2x80x9d is conducted (a step S420). Following this, the value of xe2x80x9cWxe2x80x9d which results in the minimum value of R(w)xc3x97C(w) is determined (a step S430). In obtaining the values of R(w) and C(w) in the step S430, the entries specifying the elements contained in those parts of the matrix which correspond to eliminated variables and equations and the entries specifying diagonal elements are not counted.
After the value of xe2x80x9cWxe2x80x9d has been determined, the ith and wth rows of the entry set E are replaced with each other, as well as the ith and wth columns thereof (a step S440). Then, fill-ins which take place at the time of eliminating the ith variable are computed, and entries specifying the fill-ins are added to the entry set E (a step S450).
When the step S450 is finished, the variable i is incremented by 1 (a step S460). Next, it is determined whether the value of the variable i exceeds xe2x80x9cmxe2x88x921xe2x80x9d (a step S470). When it is determined in the step S470 that the value of the variable i does not exceed mxe2x88x921, a return is made to the step S430. By repeating the steps S430 to S470, the optimum pivot order and the positions in which the fill-ins take place can be determined.
On the other hand, when it is determined in the step S470 that the value of the variable i exceeds mxe2x88x921, the coefficient matrix is compressed using the entry set E to which the entries have been added in the steps S410 and S450. Matrix data, obtained as a result of the compression, is stored in a storage area of a storage device or the like (a step S480), and the process shown in the flowchart is terminated. When the process of FIG. 11 is terminated, then the numerical calculation process is conducted.
However, the conventional process for solving the simultaneous linear equations has the following drawbacks:
Firstly, in the case where a parallel computer of distributed memory type executes the symbolic calculation process, a single node has to carry out the steps of the symbolic calculation process one after another. Under this condition, the capacity of a local memory included in the node restricts the size of the coefficient matrix which can be handled.
Secondly, in the case where the coefficient matrix which is a square matrix has a size of mxc3x97m (which indicates the number of rows and columns included in the coefficient matrix), the time required for completing the symbolic calculation process increases substantially in proportion to m1 to m3. Hence, as the coefficient matrix size becomes large and as the number of entries which are added to the entry set becomes excessive, the symbolic calculation process cannot be finished within a practical length of time.
The above-described drawbacks occur also in the case of performing a circuit simulation which entails the process for solving simultaneous linear equations.
The present invention has been made in consideration of the above drawbacks, and it is accordingly an object of the present invention to provide a symbolic calculation system and a symbolic calculation method, which can handle a large-scale matrix and whose calculation time is short.
It is another object of the present invention to provide a parallel circuit simulation system which can perform a large-scale circuit simulation at high speed.
According to the first aspect of the present invention having the above-described objects, there is provided a symbolic calculation system which performs a symbolic calculation to solve simultaneous linear equations, comprising:
a plurality of nodes each having an element processor and local memory including a program area which stores a predetermined program to be executed by the corresponding element processor and a work area used by the element processor, and an interconnection network which interconnects the plurality of nodes, wherein the element processors of the plurality of nodes are capable of cooperating with each other,
the symbolic calculation system comprising a first computer which is connected to the interconnection network, and which divides a matrix, representing the simultaneous linear equations to be solved, into a plurality of row sets each comprising at least one of rows of the matrix,
wherein each of the plurality of nodes corresponds to each row set divided by the first computer, and each of the element processor executes the predetermined program stored in the program area thereby each of the plurality of nodes:
adds entries specifying nonzero elements contained in the row sets associated with the plurality of nodes to a plurality of entry sets which are in one-to-one correspondence with the plurality of row sets;
sequentially attains a first variable which specifies an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix, by cooperating with other nodes;
replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows of the matrix, by cooperating with other nodes;
replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix, by cooperating with other nodes;
obtains fill-ins belonging to the associated row sets from a plurality of fill-ins which occur in eliminating the unknown in regard to the matrix including the rows and/or columns replaced with each other, and further adding entries specifying the obtained fill-ins to the plurality of entry sets to the entry sets.
According to this symbolic calculation systems, the plurality of nodes carry out the addition of the entries in a parallel fashion. This enables the symbolic calculation in solving the simultaneous linear equations to be performed at high speed.
In the case of realizing the aforementioned symbolic calculation systems with parallel computers of distributed memory type, the data amount corresponding to the product of the reciprocal of the number of parts in which the matrix is divided and the amount of data when a single node performs the addition of the entries to an entry set will be almost satisfactory as the amount of data to be stored in the local memory included in each of nodes which realize the plurality of first and second entry adders. In this case, the capacity of the local memory in each node does not restrict the size of the coefficient matrix which can be handled. Hence, the process for solving the simultaneous linear equations can be conducted on a large scale.
In the above-described symbolic calculation system, the first computer may be realized by any one of the plurality of nodes.
In this case, any one of the plurality of nodes may attain the first variable which determines the minimum number of calculations.
Moreover, any one of the plurality of nodes may replace one row specified by the first variable and another row specified by the second variable with each other.
Any one of the plurality of nodes may further replace one column specified by the first variable and another column specified by the second variable with each other.
The above-described symbolic calculation system may further comprise a second computer which is connected to the interconnection network and which compresses the matrix based on contents of the plurality of entry sets to which the entries have been added.
In this case, the second computer may be realized by any one of the plurality of nodes.
The above-described symbolic calculation system may further comprise a third computer which is connected to the interconnection network, and which creates a lower left rectangular matrix and an upper right triangular matrix, based on the matrix as compressed, and which performs a forward substitution with respect to the lower left rectangular matrix and performs a backward substitution with respect to the upper right rectangular matrix by using solutions obtained as a result of the forward substitution, in order to create data representing solutions of the simultaneous linear equations.
In this case, the third computer may be realized by any one of the plurality of nodes.
According to the second aspect of the present invention having the above-described objects, there is provided a symbolic calculation system which performs a symbolic calculation to solve simultaneous linear equations, comprising:
a matrix divider which divides a matrix, representing the simultaneous linear equations to be solved, into a plurality of row sets each comprising at least one of rows of the matrix;
a plurality of first entry adders, each of which is associated with one of the plurality of row sets divided by the matrix divider, and which add entries specifying nonzero elements contained in the row sets associated with the plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with the plurality of row sets;
a pivot selector which sequentially attains a first variable specifying specifies an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix;
a pivot replacer which replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows of the matrix, and replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix; and
a plurality of second entry adders, provided in one-to-one correspondence with the plurality of first entry adders, and which obtain fill-ins belonging to the associated row sets from a plurality of fill-ins that occur in eliminating the unknown in regard to the matrix including the rows and columns replaced with each other by the pivot replacer, and which add entries specifying the obtained fill-ins to the plurality of entry sets to which the entries have been added by the plurality of first entry adders that are in one-to-one correspondence with the plurality of second entry adders.
According to the third aspect of the present invention, there is provided a symbolic calculation system which performs a symbolic calculation to solve simultaneous linear equations, comprising:
a plurality of first entry adders, each of which associated with one of a plurality of row sets each comprising at least one of different rows of a matrix representing the simultaneous linear equations to be solved, and which add entries specifying nonzero elements contained in the row sets associated with the plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with the plurality of row sets;
a pivot selector which sequentially attains a first variable specifying an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix;
a pivot replacer which replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows of the matrix, and which replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix; and
a plurality of second entry adders, provided in one-to-one correspondence with the plurality of first entry adders, and which obtain fill-ins belonging to the associated row sets from a plurality of fill-ins that occur in eliminating the unknown in regard to the matrix including the rows and columns replaced with each other by the pivot replacer, and which add entries specifying the obtained fill-ins to the plurality of entry sets to which the entries have been added by the plurality of first entry adders that are in one-to-one correspondence with the plurality of second entry adders.
According to these symbolic calculation systems, the plurality of first and second entry adders carry out the addition of the entries in a parallel fashion. This enables the symbolic calculation in solving the simultaneous linear equations to be performed at high speed.
In the case of realizing the aforementioned symbolic calculation systems with parallel computers of distributed memory type, the data amount corresponding to the product of the reciprocal of the number of parts in which the matrix is divided and the amount of data when a single node performs the addition of the entries to an entry set will be almost satisfactory as the amount of data to be stored in the local memory included in each of nodes which realize the plurality of first and second entry adders. In this case, the capacity of the local memory in each node does not restrict the size of the coefficient matrix which can be handled. Hence, the process for solving the simultaneous linear equations can be conducted on a large scale.
According to the fourth aspect of the present invention having the aforementioned objects, there is provided a parallel circuit simulation system comprising:
a plurality of nodes each having an element processor and local memory including a program area which stores a predetermined program to be executed by the corresponding element processor and a work area used by the element processor, and an interconnection network which interconnects the plurality of nodes, wherein the element processors of the plurality of nodes are capable of cooperating with each other,
the parallel circuit simulation system comprising a first computer which is connected to the interconnection network, the first computer dividing a circuit to be simulated into a plurality of circuit pieces, preparing circuit piece matrix representing circuit equations corresponding to divided circuit pieces respectively, and transmitting the prepared circuit piece matrix to the plurality of nodes,
wherein each of the element processor executes the predetermined program stored in the program area thereby the plurality of nodes:
executes symbolic calculation on the circuit piece matrix transmitted by the first computer, executes numeric calculation on the result of the symbolic calculation executed by each node, and resolves the circuit equation represented by the received circuit piece matrix,
the parallel circuit simulation system comprises:
a second computer which is connected to the interconnection network, and which prepares a circuit matrix of connected circuits including connected circuit pieces, based on the obtained resolution of the circuit equation for the circuit pieces; and
a third computer which is connected to the interconnection network, and which divides the prepared circuit matrix of the connected circuits into a plurality of row sets each comprising at least one of rows of the matrix, and which transmits the plurality of row sets to the plurality of nodes respectively,
wherein each element processor executes the predetermined program stored in the program area, thereby each of the plurality of nodes further:
adds entries specifying nonzero elements contained in the row sets associated with the plurality of nodes to a plurality of entry sets which are in one-to-one correspondence with the plurality of row sets;
sequentially attains a first variable which specifies an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix, by cooperating with other nodes;
replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows of the matrix, by cooperating with other nodes;
replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix, by cooperating with other nodes;
obtains fill-ins belonging to the associated row sets from a plurality of fill-ins which occur in eliminating the unknown in regard to the matrix including the rows and/or columns replaced with each other, and further adds entries specifying the obtained fill-ins to the plurality of entry sets to the entry sets.
In the above-described parallel circuit simulation system, any of the first to third computers may be realized by any one of the plurality of nodes.
The above-described parallel circuit simulation system may further comprise a fourth computer which is connected to the interconnection network, and which compresses the matrix based on contents of the plurality of entry sets to which the entries have been added.
In this case, the fourth computer may be realized by any one of the plurality of nodes.
According to the fifth aspect of the present invention having the above-described objects, there is provided a symbolic calculation method for performing a symbolic calculation to solve simultaneous linear equations, comprising:
dividing a matrix, which represents the simultaneous linear equations to be solved, into a plurality of row sets each comprising at least one of rows of the matrix;
adding, in parallel, entries specifying nonzero elements contained in the plurality of row sets divided by the dividing to a plurality of entry sets which are in one-to-one correspondence with the plurality of row sets;
sequentially attaining a first variable which specifies an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix;
replacing one row specified by the first variable and another row specified by the second variable with each other, among the rows of the matrix, and replacing one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix; and
obtaining, in parallel, fill-ins belonging to the plurality of row sets from a plurality of fill-ins which occur in eliminating the unknown in regard to the matrix including the rows and columns replaced with each other by the replacing, and adding, in parallel, entries specifying the obtained fill-ins to the plurality of entry sets to which the entries specifying the nonzero elements contained in the plurality of row sets have been added in parallel.
The above-described symbolic calculation method may further comprise compressing the matrix, based on contents of the plurality of entry sets to which the entries specifying the nonzero elements contained in the plurality of row sets and the entries specifying the obtained fill-ins have been added.
According to the sixth aspect of the present invention having the aforementioned objects, there is provided a parallel circuit simulation system comprising:
a circuit divider which divides a circuit to be simulated into partial circuits;
a plurality of partial circuit matrix calculators, each of which is associated with one of the partial circuits divided by the circuit divider, and which creates partial circuit matrices representing circuit equations of the partial circuits associated with the plurality of partial circuit matrix calculator;
a plurality of partial circuit symbolic calculators, each of which is associated with one of the partial circuits, and which perform symbolic calculations based on the partial circuit matrices representing the circuit equations of the associated partial circuits and created by the plurality of partial circuit matrix calculators;
a plurality of partial circuit numerical calculators, each of which is associated with one of the partial circuits, and which solve the circuit equations of the associated partial circuits by performing numerical calculations using calculation results obtained as a result of the symbolic calculations which the plurality of partial circuit symbolic calculators have performed based on the partial circuit matrices representing the circuit equations of the associated circuit sections;
a combination circuit matrix calculator which creates a combination circuit matrix representing circuit equations of a combination circuit that is a combination of the partial circuits, based on solutions of the circuit equations of the partial circuits which have been solved by the plurality of partial circuit numerical calculators;
a combination circuit symbolic calculator which performs symbolic calculations based on the combination circuit matrix created by the combination circuit matrix calculator; and
a combination circuit numerical calculator which solves the circuit equations of the combination circuit by performing numerical calculations using calculation results obtained as a result of the symbolic calculations performed by the combination circuit symbolic calculator;
wherein the combination circuit symbolic calculator comprises:
a matrix divider which divides the combination circuit matrix into a plurality of row sets each comprising at least one of rows of the combination circuit matrix;
a plurality of first entry adders, each of which is associated with one of the plurality of row sets divided by the matrix divider, and which add entries specifying nonzero elements contained in the row sets associated with the plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with the plurality of row sets;
a pivot selector which sequentially attains a first variable specifying specifies an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the combination circuit matrix;
a pivot replacer which replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows of the combination circuit matrix, and which replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the combination circuit matrix; and
a plurality of second entry adders, provided in one-to-one correspondence with the plurality of first entry adders, and which obtain fill-ins belonging to the associated row sets from a plurality of fill-ins which occur in eliminating the unknown in regard to the combination circuit matrix including the rows and columns replaced with each other by the pivot replacer, and which add entries specifying the obtained fill-ins to the plurality of entry sets to which the entries have been added by the plurality of first entry adders that are in one-to-one correspondence with the plurality of second entry adders.
According to the seventh aspect of the present invention having the aforementioned objects, there is provided a computer usable storage medium containing a computer readable program stored therein for causing a computer to serve as:
a matrix divider which divides a matrix, representing simultaneous linear equations to be solved, into a plurality of row sets each comprising at least one of rows of the matrix;
a plurality of first entry adders, each of which is associated with one of the plurality of row sets divided by the matrix divider, and which add entries specifying nonzero elements contained in the row sets associated with the plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with the plurality of row sets;
a pivot selector which sequentially attains a first variable specifying an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix;
a pivot replacer which replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows included in the matrix, and replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix; and
a plurality of second entry adders, provided in one-to-one correspondence with the plurality of first entry adders, and which obtain fill-ins belonging to the associated row sets from a plurality of fill-ins that occur in eliminating the unknown in regard to the matrix including the rows and columns replaced with each other by the pivot replacer, and add entries specifying the obtained fill-ins to the plurality of entry sets to which the entries have been added by the plurality of first entry adders that are in one-to-one correspondence with the plurality of second entry adders.
According to the eighth aspect of the present invention having the aforementioned objects, there is provided a program signal embedded in a carrier wave, for causing a computer to serve as:
a matrix divider which divides a matrix, representing simultaneous linear equations to be solved, into a plurality of row sets each comprising at least one of rows of the matrix;
a plurality of first entry adders, each of which is associated with one of the plurality of row sets divided by the matrix divider, and which add entries specifying nonzero elements contained in the row sets associated with the plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with the plurality of row sets;
a pivot selector which sequentially attains a first variable specifying specifies an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix;
a pivot replacer which replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows of the matrix, and which replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix; and
a plurality of second entry adders, provided in one-to-one correspondence with the plurality of first entry adders, and which obtain fill-ins belonging to the associated row sets from a plurality of fill-ins that occur in eliminating the unknown in regard to the matrix including the rows and columns replaced with each other by the pivot selector, and which add entries specifying the obtained fill-ins to the plurality of entry sets to which the entries have been added by the plurality of first entry adders that are in one-to-one correspondence with the plurality of second entry adders.